Crack the Power
We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.
Crack the Power
We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.
Information Given
Description
We received an encrypted message. The modulus is built from primes large enough that factoring them isn't an option, at least not today. See if you can make sense of the numbers and reveal the flag.
Download the message.
Hints
- • When certain values in the encryption setup are smaller than usual, it opens up unexpected shortcuts to recover the plaintext
- • Consider whether you can invert the encryption without factoring
n - • Read more about Coppersmith's attack
Message
We received an encrypted message. See if you can make sense of the numbers and reveal the flag.
We are given:
We're given an RSA encrypted message with the following parameters:
- • n: A very large 2048-bit modulus
- • e: 20 (unusually small public exponent)
- • c: The ciphertext
n = 410664186165191791402826020648772079727855370225121168329489558023676206903110917122249911944501914058167574154300515578639528319920053023867482073692484985287827372248686968550452147219495058219737726533198589146788106207104006141113375574066854852611259725786317821883172497842657985257908701482139090568993822965683214349918502719101583356882168338270447984584381812927858227415072514189838197665563968909219013964220237934124402478909876364171409578837503118525132848891505287317986848688438750873278654357181872934401664809196436196103395671068981692006881025785118124735403009761732676194557783341186696317289217601680762240946756099165359859285900990663149297784065325172930606950668533524438921457116354261722563783316401034088432522913099965625002265981169229586378601077820521982226216733874547440407450338648780337291742094848216093949046938054996321130253196977418170117347647315719448397122004966163394965123751185910309725139116961163368621449406198577849587926254211380551265442088456309106778455980283046226445371066856262215933615411567261989837352437927401685169541910706297673710978352664847844643089079402646094504545790754030992062817610552755382423490304761138904591244735268207666957111641348148546651263055711 e = 20 c = 640637430810406857500566702096274079868087131935153057078985716461078483409793615804311883296591203324452249008450521032645267345512046769994383635285244380705157432625570066632528925314552900669814963219369331313157534607620352061314683496525883016843153241425770911702563380247302073740850825452371063276867610414725164654421304873071774234683226777641240092032528116047489137507373500064099947304524782898265669628686091404044097235795818651902023996906668123465373292221934136216954999213086853380479136606214034827032162211811911299453884553459883192781319337391984912950371275232374262114220706295073924345743106413419931715570201067076471272561731959500262271837841417300230554359594018424813861589485400512131504027368400263321851762034719595379735999122340323973277638235482616225404363214027767922993075345559200374830345517529445328472713066257434684134913873359589576414681791333170123047390862933633440111883394760439698156048278154619895786259579727797488066274962774692244105308866923365722966155030681035814505674226605348055192323888099731031683511808581367884577911318683020417249790405911629045010877656025044271667195964670746001
Solve Script
from gmpy2 import iroot
# Given values
n = 410664186165191791402826020648772079727855370225121168329489558023676206903110917122249911944501914058167574154300515578639528319920053023867482073692484985287827372248686968550452147219495058219737726533198589146788106207104006141113375574066854852611259725786317821883172497842657985257908701482139090568993822965683214349918502719101583356882168338270447984584381812927858227415072514189838197665563968909219013964220237934124402478909876364171409578837503118525132848891505287317986848688438750873278654357181872934401664809196436196103395671068981692006881025785118124735403009761732676194557783341186696317289217601680762240946756099165359859285900990663149297784065325172930606950668533524438921457116354261722563783316401034088432522913099965625002265981169229586378601077820521982226216733874547440407450338648780337291742094848216093949046938054996321130253196977418170117347647315719448397122004966163394965123751185910309725139116961163368621449406198577849587926254211380551265442088456309106778455980283046226445371066856262215933615411567261989837352437927401685169541910706297673710978352664847844643089079402646094504545790754030992062817610552755382423490304761138904591244735268207666957111641348148546651263055711
e = 20
c = 640637430810406857500566702096274079868087131935153057078985716461078483409793615804311883296591203324452249008450521032645267345512046769994383635285244380705157432625570066632528925314552900669814963219369331313157534607620352061314683496525883016843153241425770911702563380247302073740850825452371063276867610414725164654421304873071774234683226777641240092032528116047489137507373500064099947304524782898265669628686091404044097235795818651902023996906668123465373292221934136216954999213086853380479136606214034827032162211811911299453884553459883192781319337391984912950371275232374262114220706295073924345743106413419931715570201067076471272561731959500262271837841417300230554359594018424813861589485400512131504027368400263321851762034719595379735999122340323973277638235482616225404363214027767922993075345559200374830345517529445328472713066257434684134913873359589576414681791333170123047390862933633440111883394760439698156048278154619895786259579727797488066274962774692244105308866923365722966155030681035814505674226605348055192323888099731031683511808581367884577911318683020417249790405911629045010877656025044271667195964670746001
# Direct root extraction attack
m, is_exact_root = iroot(c, e)
if is_exact_root:
# Convert to bytes and decode
flag_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
flag = flag_bytes.decode('ascii')
print(f"Flag: {flag}")
else:
print("Direct root failed - would need Coppersmith's attack")To be able to run this:
pip install gmpy2This leaves us with the flag: picoCTF{t1ny_e_381870dd}